import time
import numpy as np


def look_for(L, left, right):
    if left >= right:
        return L[left]
    # 产生随机索引号
    m = np.random.randint(left, right)
    n = L[left]
    L[left] = L[m]
    # 完成随机值与left交换
    L[m] = n

    i = left
    j = right
    key = L[left]
    while i < j:
        while i < j and key <= L[j]:
            j -= 1
        # 从右往左找到一个比key小的，将其赋值给基准值
        L[i] = L[j]
        while i < j and L[i] <= key:
            i += 1
        # 从左往右找到一个比key大的，将其赋值给基准值
        L[j] = L[i]
    L[i] = key
    # 已完成左侧比key小，右侧比key大
    # 判断i是否为数组的中间索引
    # 偶数的中间索引
    if len(L) % 2 == 0 and i == int(len(L) / 2) - 1:
        return key
    # 奇数的中间索引
    elif len(L) % 2 != 0 and i == int(len(L) / 2):
        return key
    # 如果i大于中间索引则递归数组左边部分
    if i > int(len(L) / 2) - 1:
        return look_for(L, left, i - 1)
    else:
        # 反之递归数组右边部分
        return look_for(L, i + 1, right)


def main():
    length = int(input("请输入规模："))
    result = np.random.randint(-2 ** 31, 2 ** 31 - 1, length).tolist()
    start = time.perf_counter()
    mid = look_for(result, 0, len(result) - 1)
    end = time.perf_counter()
    print("共耗时:%f\n" % (end - start))
    print("中间值为：%d" % mid)


if __name__ == '__main__':
    main()
